package _17_剑指Offer;

public class _45_剑指Offer把数组排成最小的数 {

    public static void main(String[] args) {

        _45_剑指Offer把数组排成最小的数 v = new _45_剑指Offer把数组排成最小的数();

        int[] ins = new int[]{1, 2, 3, 1};
        System.out.println(v.minNumber(ins));
    }

    // 使用快速排序优化
    public String minNumber(int[] nums) {
        String[] str = new String[nums.length];
        for (int i = 0; i < nums.length; i++) {
            str[i] = String.valueOf(nums[i]);
        }
        quickSort(str, 0, nums.length - 1);
        StringBuilder sb = new StringBuilder();
        for (String str1 : str) {
            sb.append(str1);
        }
        return sb.toString();
    }

    public void quickSort(String[] str, int begin, int end) {
        if (begin >= end) return;

        // 构造轴点元素
        int mid = pivotIndex(str, begin, end);
        quickSort(str, begin, mid - 1);
        quickSort(str, mid + 1, end);
    }

    private int pivotIndex(String[] str, int begin, int end) {
        String pivot = str[begin]; // 1
        while (begin < end) {
            while (begin < end) {
                if ((str[end] + pivot).compareTo(pivot + str[end]) > 0) end--;
                else {
                    str[begin++] = str[end];
                    break;
                }
            }
            while (begin < end) {
                if ((str[begin] + pivot).compareTo(pivot + str[begin]) < 0) begin++;
                else {
                    str[end--] = str[begin];
                    break;
                }
            }
        }
        str[begin] = pivot;
        return begin;
    }

    // 将数组中的所有元素，排除最小的复杂度为n^2
    public String minNumber1(int[] nums) {
        for (int i = 1; i < nums.length; i++) {
            int swapIndex = i;
            for (int j = i - 1; j >= 0; j--) {
                String prevStr = String.valueOf(nums[j]);
                String curStr = String.valueOf(nums[swapIndex]);
                if (Long.parseLong(prevStr + curStr) > Long.parseLong(curStr + prevStr)) {
                    // 交换元素位置
                    int temp = nums[swapIndex];
                    nums[swapIndex] = nums[j];
                    nums[j] = temp;
                    swapIndex = j;
                }
            }
        }
        StringBuilder sb = new StringBuilder();
        for (int num : nums) {
            sb.append(num);
        }
        return sb.toString();
    }


}
